1 00:00:02,840 --> 00:00:03,840 Codificado por 2 00:00:04,040 --> 00:00:07,840 Sem que percebamos, a vida moderna foi tomada. 3 00:00:10,080 --> 00:00:14,480 Enquanto procuramos pelo amor, faça compras online, 4 00:00:14,480 --> 00:00:18,000 viajar pelo mundo, 5 00:00:18,000 --> 00:00:20,320 mesmo quando salvamos vidas, 6 00:00:20,320 --> 00:00:25,160 há instruções passo a passo trabalhando silenciosamente nos bastidores. 7 00:00:27,080 --> 00:00:30,440 Cada vez mais, eles estão governando nossas vidas. 8 00:00:30,440 --> 00:00:33,040 Eles são chamados de algoritmos. 9 00:00:34,400 --> 00:00:36,640 Algoritmos estão por toda parte. 10 00:00:36,640 --> 00:00:39,680 Esses pequenos pedaços de matemática tornaram-se centrais 11 00:00:39,680 --> 00:00:41,520 para nossas vidas diárias. 12 00:00:41,520 --> 00:00:44,800 Mas porque são invisíveis, tendemos a considerá-los garantidos, 13 00:00:44,800 --> 00:00:46,320 até mesmo entendê-los mal. 14 00:00:50,960 --> 00:00:52,080 RISOS 15 00:00:53,200 --> 00:00:57,040 Eles são o segredo do nosso mundo digital e muito mais. 16 00:00:58,720 --> 00:01:02,120 'Neste programa, vou mostrar alguns dos meus favoritos 17 00:01:02,120 --> 00:01:05,880 'algoritmos para revelar de onde eles vieram...' 18 00:01:05,880 --> 00:01:08,480 Algoritmos são antigos. 19 00:01:08,480 --> 00:01:09,800 '..como eles funcionam...' 20 00:01:09,800 --> 00:01:11,920 O desafio é encontrar o caminho mais curto... 21 00:01:11,920 --> 00:01:14,640 Estas são as instruções aproximadas que você usaria. 22 00:01:14,640 --> 00:01:17,800 ..para retornar ao seu ponto de partida. 23 00:01:17,800 --> 00:01:20,240 '..o que eles poderão fazer no futuro.' 24 00:01:20,240 --> 00:01:23,440 - O algoritmo está se escrevendo? Ou...? - Absolutamente. 25 00:01:23,440 --> 00:01:26,080 '..e como não podemos viver sem eles.' 26 00:01:26,080 --> 00:01:29,600 Mesmo quando estamos fazendo um bolo, estamos seguindo um algoritmo. 27 00:01:29,600 --> 00:01:32,520 Como matemático, adoro algoritmos. 28 00:01:32,520 --> 00:01:35,120 Eles não são apenas solucionadores de problemas impressionantes, 29 00:01:35,120 --> 00:01:38,800 mas também estranhamente bonito, explorando a matemática 30 00:01:38,800 --> 00:01:42,200 ordem que sustenta o modo como o universo funciona. 31 00:01:42,200 --> 00:01:45,760 Bem-vindo ao estranho e maravilhoso mundo dos algoritmos. 32 00:01:54,600 --> 00:01:57,680 A maioria de nós carrega um desses por aí. 33 00:01:57,680 --> 00:02:00,160 Agora, você deve ter notado que quando tira uma foto 34 00:02:00,160 --> 00:02:05,800 com o seu telefone, ele desenha uma caixa ao redor de qualquer rosto, assim. 35 00:02:05,800 --> 00:02:09,480 Este é o resultado de um algoritmo especial de detecção de rosto 36 00:02:09,480 --> 00:02:13,200 e ajuda a manter o rosto da foto em foco. 37 00:02:14,480 --> 00:02:18,280 'Como todos os algoritmos, este resolve um problema. 38 00:02:18,280 --> 00:02:21,520 'Neste caso, encontrar um rosto humano. 39 00:02:21,520 --> 00:02:24,760 'Embora não se deixe enganar por uma cara feita de fruta, 40 00:02:24,760 --> 00:02:28,400 'ele detecta um rosto humano em uma foto. 41 00:02:28,400 --> 00:02:31,200 'Então, como isso acontece? 42 00:02:31,200 --> 00:02:34,120 'Na sua raiz, os algoritmos são pouco mais do que 43 00:02:34,120 --> 00:02:37,280 'uma série de instruções passo a passo. 44 00:02:37,280 --> 00:02:40,520 'Este funciona escaneando metodicamente a imagem 45 00:02:40,520 --> 00:02:43,520 'procurando por quatro padrões abstratos específicos 46 00:02:43,520 --> 00:02:45,960 'associado a um rosto. 47 00:02:45,960 --> 00:02:48,280 'Quando estes são detectados um após o outro, 48 00:02:48,280 --> 00:02:52,520 'então o algoritmo indica que encontrou um rosto humano.' 49 00:02:52,520 --> 00:02:56,880 O processo explora o padrão subjacente por trás de todos os rostos, 50 00:02:56,880 --> 00:02:59,520 não importa a forma ou tamanho. 51 00:02:59,520 --> 00:03:02,840 O resultado final é apenas um exemplo de como os algoritmos 52 00:03:02,840 --> 00:03:05,560 tornou nossas vidas mais fáceis. 53 00:03:05,560 --> 00:03:09,000 - Eu farei isso! - Eu farei isso! - Eu cheguei aqui primeiro! - OK. 54 00:03:09,000 --> 00:03:10,600 Então, vá embora. 55 00:03:10,600 --> 00:03:14,240 'Temos a tendência de associar algoritmos a computadores, smartphones 56 00:03:14,240 --> 00:03:15,480 'e a internet. 57 00:03:15,480 --> 00:03:19,320 'Mas eles não são exclusivos do mundo da tecnologia. 58 00:03:19,320 --> 00:03:24,160 'Meu trabalho diário é professor de matemática na Universidade de Oxford. 59 00:03:24,160 --> 00:03:26,920 'E uma das coisas que mais gosto é manter 60 00:03:26,920 --> 00:03:29,120 'os alunos na ponta dos pés.' 61 00:03:29,120 --> 00:03:31,040 OK, vou pegar um. 62 00:03:31,040 --> 00:03:33,920 Aqui, estamos jogando um jogo matemático com uma jarra 63 00:03:33,920 --> 00:03:37,120 cheio de chocolates e uma pimenta vermelha. 64 00:03:38,480 --> 00:03:42,720 “O objetivo é não ficar com a pimenta no final. 65 00:03:42,720 --> 00:03:44,360 'Mas o que esses estudantes não sabem, 66 00:03:44,360 --> 00:03:49,520 'é que estou jogando com a ajuda de um algoritmo.' 67 00:03:49,520 --> 00:03:51,800 - OK. Preparar? AMBOS: - Sim. 68 00:03:51,800 --> 00:03:54,560 Certo, eu vou primeiro, então lembre-se, você pode pegar um, 69 00:03:54,560 --> 00:03:57,200 dois ou três chocolates de cada vez. 70 00:03:57,200 --> 00:04:00,880 Não sou um cara ganancioso, então vou pegar um. Agora é sua vez. 71 00:04:00,880 --> 00:04:05,440 'Cada jogador joga na sua vez, entre um e três chocolates.' 72 00:04:05,440 --> 00:04:09,120 Você pegou dois, ok. Então, eu vou levar... vou levar dois. 73 00:04:09,120 --> 00:04:12,280 'O que quer que meu oponente faça, meu algoritmo me diz 74 00:04:12,280 --> 00:04:14,200 'como responder.' 75 00:04:14,200 --> 00:04:16,520 OK, vou levar dois. 76 00:04:16,520 --> 00:04:19,080 E sua vez novamente. ELA RI 77 00:04:19,080 --> 00:04:20,680 Ah, sim. 78 00:04:20,680 --> 00:04:24,040 - Então vou levar... três. - Três. E eu vou pegar um. 79 00:04:24,040 --> 00:04:27,160 - E só sobrou uma pimenta... - Então, espere. Sou eu? - Sim, então você tem 80 00:04:27,160 --> 00:04:29,640 - para comer a pimenta. - Oh não! - Então, aí está. 81 00:04:29,640 --> 00:04:32,960 'Deixe-me revelar como o algoritmo que eu estava usando me ajudou a vencer.' 82 00:04:32,960 --> 00:04:34,520 É a única maneira de aprender. 83 00:04:35,680 --> 00:04:40,680 Portanto, a chave é pensar em agrupar as coisas em quatro. 84 00:04:41,960 --> 00:04:46,720 13 chocolates divididos em três grupos de quatro, sobrando um. 85 00:04:46,720 --> 00:04:50,160 Então, pegando um chocolate na primeira rodada e depois quatro 86 00:04:50,160 --> 00:04:54,160 menos tudo o que o outro jogador fizer nas rodadas subsequentes, 87 00:04:54,160 --> 00:04:57,040 este algoritmo garante que o outro jogador 88 00:04:57,040 --> 00:04:58,960 sempre fica com a pimenta. 89 00:04:58,960 --> 00:05:01,080 A essência de um realmente bom 90 00:05:01,080 --> 00:05:04,240 algoritmo, sua mágica, se você preferir, é a matemática. 91 00:05:04,240 --> 00:05:07,440 Os melhores algoritmos são aqueles que exploram o subjacente 92 00:05:07,440 --> 00:05:10,400 estrutura matemática escondida sob um problema. 93 00:05:11,600 --> 00:05:13,080 OK, coloque a pimenta de volta. 94 00:05:14,480 --> 00:05:17,760 Apresentarei a você alguns dos algoritmos que 95 00:05:17,760 --> 00:05:20,320 tornar-se o coração pulsante da vida moderna. 96 00:05:21,880 --> 00:05:24,920 Mas primeiro, quero mostrar-lhe que, apesar de todas as suas características modernas 97 00:05:24,920 --> 00:05:28,360 aplicações, os algoritmos são extremamente antigos. 98 00:05:29,680 --> 00:05:33,600 Na verdade, eles são milhares de anos anteriores aos computadores. 99 00:05:35,480 --> 00:05:38,280 O algoritmo mais antigo que conhecemos foi desenvolvido 100 00:05:38,280 --> 00:05:40,480 para resolver um problema matemático. 101 00:05:40,480 --> 00:05:44,800 Foi escrito pela primeira vez pelo matemático grego antigo Euclides. 102 00:05:44,800 --> 00:05:47,520 O Algoritmo de Euclides, como é conhecido, 103 00:05:47,520 --> 00:05:50,680 é um método para encontrar o maior divisor comum. 104 00:05:52,360 --> 00:05:55,680 O maior divisor comum é o maior número que 105 00:05:55,680 --> 00:06:00,280 divida em um par de outros números sem deixar resto. 106 00:06:00,280 --> 00:06:03,000 Então, neste caso, quatro divide em oito 107 00:06:03,000 --> 00:06:06,080 e 12 sem resto. 108 00:06:06,080 --> 00:06:08,520 É simples encontrar números pequenos, 109 00:06:08,520 --> 00:06:10,600 mas muito mais complicado para os grandes. 110 00:06:12,120 --> 00:06:15,480 Embora Euclides tenha sido o maior matemático de sua época, 111 00:06:15,480 --> 00:06:18,640 seu algoritmo poderia ter lhe rendido uma fortuna como ladrilhador. 112 00:06:19,840 --> 00:06:22,280 Deixe-me mostrar por quê. 113 00:06:22,280 --> 00:06:25,440 Imagine que você tem um piso retangular 114 00:06:25,440 --> 00:06:26,760 e você quer encontrar 115 00:06:26,760 --> 00:06:30,360 a maneira mais eficiente de revestir com ladrilhos quadrados. 116 00:06:30,360 --> 00:06:34,080 Em outras palavras, qual é o maior ladrilho quadrado que irá exatamente 117 00:06:34,080 --> 00:06:38,040 dividir as dimensões do piso sem sobrar nada? 118 00:06:38,040 --> 00:06:40,440 Esta é, na verdade, uma versão geométrica 119 00:06:40,440 --> 00:06:43,080 do maior problema comum do devisor. 120 00:06:43,080 --> 00:06:46,280 As dimensões do piso são os dois números 121 00:06:46,280 --> 00:06:48,640 e o tamanho das peças, que vamos tentar 122 00:06:48,640 --> 00:06:51,960 e malhar, é o seu maior inventor comum. 123 00:06:54,040 --> 00:06:57,480 Vamos seguir passo a passo o Algoritmo de Euclides para mostrar 124 00:06:57,480 --> 00:07:01,480 como é possível encontrar o ladrilho quadrado de tamanho perfeito para este piso. 125 00:07:02,920 --> 00:07:06,800 De acordo com o Algoritmo de Euclides, precisamos começar a preencher o retângulo 126 00:07:06,800 --> 00:07:10,960 com ladrilhos quadrados correspondentes à menor das duas dimensões. 127 00:07:13,760 --> 00:07:15,920 Esta é a primeira etapa do trabalho. 128 00:07:17,160 --> 00:07:19,040 O Algoritmo de Euclides então nos diz 129 00:07:19,040 --> 00:07:22,400 fazer exatamente a mesma coisa novamente com este retângulo. 130 00:07:24,080 --> 00:07:28,520 Em cada estágio, o algoritmo nos diz para selecionar peças quadradas 131 00:07:28,520 --> 00:07:31,600 correspondente ao lado mais curto do retângulo. 132 00:07:33,600 --> 00:07:38,880 Então, desta vez, nossos ladrilhos quadrados preenchem perfeitamente o espaço restante. 133 00:07:38,880 --> 00:07:42,960 Agora, meu ladrilho quadrado tem dimensões 15x15. 134 00:07:42,960 --> 00:07:45,720 Então o Algoritmo de Euclides nos diz 135 00:07:45,720 --> 00:07:50,440 que o maior divisor comum de 150 e 345 é 15. 136 00:07:53,240 --> 00:07:56,160 Não estou sugerindo que você use o Algoritmo de Euclides sempre 137 00:07:56,160 --> 00:07:58,360 você precisa encomendar algumas peças, 138 00:07:58,360 --> 00:08:02,480 mas o incrível é que esse método simples passo a passo 139 00:08:02,480 --> 00:08:06,440 encontra o ladrilho quadrado perfeito, independentemente das dimensões do piso. 140 00:08:07,800 --> 00:08:11,640 O Algoritmo de Euclides pode parecer apenas uma técnica matemática, 141 00:08:11,640 --> 00:08:16,400 mas cumpre com muita elegância todos os critérios de um algoritmo. 142 00:08:16,400 --> 00:08:20,120 É um conjunto de instruções precisamente indicado, o procedimento 143 00:08:20,120 --> 00:08:24,800 sempre termina e pode-se comprovar que funciona em todos os casos. 144 00:08:28,320 --> 00:08:31,800 O poder dos algoritmos é que você não precisa reinventar 145 00:08:31,800 --> 00:08:36,480 a roda de cada vez. São soluções gerais para problemas. 146 00:08:36,480 --> 00:08:40,000 Isso vale tanto para algoritmos antigos quanto para algoritmos modernos. 147 00:08:45,320 --> 00:08:49,480 Em 1998 nesta garagem em Menlo Park na Califórnia 148 00:08:49,480 --> 00:08:52,440 uma importante peça da história algorítmica foi feita. 149 00:08:54,520 --> 00:08:58,560 Lá dentro estavam dois estudantes de doutorado da Universidade de Stamford. 150 00:08:58,560 --> 00:09:00,760 Larry Page e Sergey Brin. 151 00:09:02,320 --> 00:09:05,640 O objetivo deles era criar um mecanismo de busca que pudesse encontrar 152 00:09:05,640 --> 00:09:08,480 coisas de forma eficiente na World Wide Web. 153 00:09:11,000 --> 00:09:13,880 Desses começos humildes, nasceu o Google. 154 00:09:15,400 --> 00:09:18,760 Mas o Google não seria Google se não fosse pelo algoritmo que 155 00:09:18,760 --> 00:09:21,600 Larry e Sergey criaram, chamado PageRank. 156 00:09:30,880 --> 00:09:34,040 PageRank foi o algoritmo central do primeiro 157 00:09:34,040 --> 00:09:37,200 encarnação do mecanismo de busca Google. 158 00:09:37,200 --> 00:09:42,120 Agora, tecnicamente, não é um algoritmo de busca, mas um algoritmo de classificação. 159 00:09:42,120 --> 00:09:45,600 Então, quando você digita uma consulta em um mecanismo de pesquisa, 160 00:09:45,600 --> 00:09:49,880 então existem literalmente milhões de páginas que corresponderão a essa consulta. 161 00:09:49,880 --> 00:09:53,600 O que o PageRank faz é classificar todas essas páginas para que aquela 162 00:09:53,600 --> 00:09:56,960 no topo está aquele em que você provavelmente estará interessado. 163 00:09:58,520 --> 00:10:01,440 Larry e Sergey tiveram a ideia de fazer o PageRank 164 00:10:01,440 --> 00:10:05,880 e usá-lo como um sistema de classificação para melhorar a qualidade da pesquisa na web. 165 00:10:05,880 --> 00:10:07,800 Eu me lembro de mim mesmo naquela época, 166 00:10:07,800 --> 00:10:10,720 você usou um mecanismo de pesquisa na web como o AltaVista. 167 00:10:10,720 --> 00:10:12,760 Você teria que clicar no link Próxima página 168 00:10:12,760 --> 00:10:14,880 muitas vezes para encontrar o que você procurava. 169 00:10:14,880 --> 00:10:17,280 O PageRank foi uma das razões pelas quais o Google foi 170 00:10:17,280 --> 00:10:20,760 muito melhor do que os motores de busca existentes na época. 171 00:10:21,800 --> 00:10:24,840 O funcionamento interno do PageRank está oculto 172 00:10:24,840 --> 00:10:26,680 na rede mundial de computadores. 173 00:10:26,680 --> 00:10:30,360 Então, para revelar como ele faz seu trabalho, usaremos o PageRank 174 00:10:30,360 --> 00:10:33,440 algoritmo para classificar os jogadores de um time de futebol. 175 00:10:34,600 --> 00:10:36,960 O PageRank analisa duas coisas. 176 00:10:36,960 --> 00:10:42,040 Ele analisa os links recebidos para uma página da web, ou seja, as outras páginas 177 00:10:42,040 --> 00:10:46,360 esse link para a página e analisa a importância dessas páginas. 178 00:10:51,960 --> 00:10:54,840 Em nossa demonstração para mostrar a inteligência do PageRank 179 00:10:54,840 --> 00:10:59,280 algoritmo, os jogadores do time de futebol são as páginas da web 180 00:10:59,280 --> 00:11:02,880 e os passes entre eles são os links da web. 181 00:11:02,880 --> 00:11:05,680 A entrada para o algoritmo. 182 00:11:05,680 --> 00:11:09,240 De modo geral, o algoritmo PageRank fornecerá um valor mais alto 183 00:11:09,240 --> 00:11:13,240 classificação para um site se ele tiver muitos links provenientes de outros sites. 184 00:11:13,240 --> 00:11:16,000 Assim, no caso do futebol, se um jogador conseguir mais 185 00:11:16,000 --> 00:11:20,080 passes do resto da equipe, então eles terão uma classificação mais elevada. 186 00:11:20,080 --> 00:11:21,680 Não é tão simples. 187 00:11:21,680 --> 00:11:24,960 Porque o algoritmo PageRank realmente dá mais peso aos 188 00:11:24,960 --> 00:11:28,880 um link de um site que possui um page rank alto. 189 00:11:28,880 --> 00:11:32,520 Na verdade, um passe de um jogador popular vale mais do que 190 00:11:32,520 --> 00:11:35,960 um passe de um jogador que quase não está envolvido no jogo. 191 00:11:37,120 --> 00:11:40,920 Esta é uma visualização do algoritmo em funcionamento. 192 00:11:40,920 --> 00:11:45,880 As estatísticas são a classificação atual dos jogadores. A saída do algoritmo. 193 00:11:45,880 --> 00:11:50,280 E cada vez que há uma aprovação, essas classificações são atualizadas. 194 00:11:50,280 --> 00:11:56,360 Quando o Google usa esse algoritmo, ele muda apenas uma coisa: a entrada. 195 00:11:56,360 --> 00:11:59,280 No lugar dos passes, usa links da web. 196 00:12:01,280 --> 00:12:04,320 Observe que a importância de uma página depende da importância 197 00:12:04,320 --> 00:12:06,480 das páginas vinculadas a ele. 198 00:12:06,480 --> 00:12:09,160 Isso significa que você deve calcular o page rank para todos 199 00:12:09,160 --> 00:12:11,240 as páginas ao mesmo tempo. 200 00:12:11,240 --> 00:12:14,200 E você realmente tem que repetir o cálculo porque, cada vez, 201 00:12:14,200 --> 00:12:16,600 você atualizará a importância de todas as páginas. 202 00:12:16,600 --> 00:12:19,040 E isso, por sua vez, influenciará 203 00:12:19,040 --> 00:12:22,120 a importância das páginas às quais essas páginas estão vinculadas. 204 00:12:30,680 --> 00:12:33,840 Ao final da partida, o trabalho do algoritmo está concluído. 205 00:12:36,720 --> 00:12:39,880 Se quiséssemos procurar o jogador-chave da equipe, 206 00:12:39,880 --> 00:12:41,840 esta é a resposta do PageRank. 207 00:12:43,800 --> 00:12:46,400 O jogador 11 tem a pontuação mais alta no PageRank. 208 00:12:48,320 --> 00:12:50,640 Acho que o algoritmo PageRank é provavelmente 209 00:12:50,640 --> 00:12:52,560 meu algoritmo favorito de todos os tempos. 210 00:12:52,560 --> 00:12:54,960 E é incrível que isso possa ser aplicado não apenas para 211 00:12:54,960 --> 00:12:58,520 na World Wide Web, mas também analisando uma partida de futebol. 212 00:12:58,520 --> 00:13:01,320 Mas para mim, é o fato de que há um belo pedaço de 213 00:13:01,320 --> 00:13:03,880 matemática em seu cerne que sempre parece encontrar 214 00:13:03,880 --> 00:13:05,960 o site que estou procurando. 215 00:13:08,120 --> 00:13:09,320 Dentro do Google, acho 216 00:13:09,320 --> 00:13:14,320 O PageRank é visto como uma parte muito importante do desenvolvimento inicial do Google. 217 00:13:15,520 --> 00:13:18,600 O PageRank era o segredo do motivo pelo qual o mecanismo de busca que Larry 218 00:13:18,600 --> 00:13:22,200 e Sergey, construído na década de 1990, teve muito sucesso. 219 00:13:23,920 --> 00:13:28,640 Agora, o Google lida com mais de 3,5 bilhões de pesquisas todos os dias. 220 00:13:28,640 --> 00:13:31,960 É o mecanismo de busca mais popular do mundo. 221 00:13:31,960 --> 00:13:36,480 E a empresa vale mais de 450 bilhões. 222 00:13:37,560 --> 00:13:40,760 Nada mal para dois estudantes de doutorado trabalhando em uma garagem. 223 00:13:49,000 --> 00:13:52,600 Algoritmos são receitas simples passo a passo. 224 00:13:52,600 --> 00:13:56,800 Inventá-los requer criatividade e genialidade incríveis. 225 00:13:56,800 --> 00:14:01,000 Mas usá-los é apenas uma questão de seguir as instruções. 226 00:14:01,000 --> 00:14:04,600 E é por isso que os algoritmos são perfeitos para computadores. 227 00:14:08,240 --> 00:14:10,200 Os computadores são apenas máquinas. 228 00:14:10,200 --> 00:14:14,000 Eles apenas realizam tarefas repetitivas em velocidades fenomenais. 229 00:14:14,000 --> 00:14:15,560 Velocidades inacreditáveis. 230 00:14:15,560 --> 00:14:20,080 Então eles são absolutamente perfeitos para realizar essas tarefas repetitivas 231 00:14:20,080 --> 00:14:23,120 que são inequivocamente definidos 232 00:14:23,120 --> 00:14:27,320 e pode ser feito em um período de tempo finito. 233 00:14:29,040 --> 00:14:32,040 O código de computador basicamente torna um algoritmo específico. 234 00:14:32,040 --> 00:14:33,840 Portanto, o algoritmo é o tipo de ideia. 235 00:14:33,840 --> 00:14:35,280 Como você resolveria o problema? 236 00:14:35,280 --> 00:14:37,680 Estas são as instruções aproximadas que você usaria. 237 00:14:37,680 --> 00:14:40,760 E então isso pode ser traduzido em um código específico. 238 00:14:43,920 --> 00:14:47,880 Muitos tipos de algoritmos foram criados com um computador em mente. 239 00:14:49,800 --> 00:14:53,360 E alguns dos mais importantes são algoritmos de classificação. 240 00:14:54,880 --> 00:14:58,880 Agora, a tarefa de um algoritmo de classificação é colocar as coisas em ordem. 241 00:14:58,880 --> 00:15:00,560 E eles têm muitos usos. 242 00:15:00,560 --> 00:15:03,720 Por exemplo, na internet, a informação é obtida 243 00:15:03,720 --> 00:15:08,720 dividido em pacotes de dados que são enviados pela web. 244 00:15:08,720 --> 00:15:11,000 Agora, para remontar esses dados, 245 00:15:11,000 --> 00:15:15,120 algoritmos de classificação são absolutamente cruciais para colocar esses dados 246 00:15:15,120 --> 00:15:18,720 de volta na ordem correta para que possamos ver a imagem, 247 00:15:18,720 --> 00:15:21,560 ou leia o e-mail que acabamos de receber. 248 00:15:26,120 --> 00:15:30,000 Esta é a System Development Corporation na Califórnia. 249 00:15:30,000 --> 00:15:35,560 É considerada a primeira empresa de software de computador do mundo. 250 00:15:35,560 --> 00:15:40,680 E foi aqui, em 1963, que dois cientistas da computação formalmente 251 00:15:40,680 --> 00:15:44,360 escreveu um dos algoritmos de classificação mais icônicos de todos os tempos. 252 00:15:48,240 --> 00:15:50,280 É chamado de classificação por bolha. 253 00:15:50,280 --> 00:15:53,520 E aqui está um exemplo de classificação por bolha em ação, 254 00:15:53,520 --> 00:15:55,920 classificando blocos em vez de números. 255 00:15:57,720 --> 00:16:01,200 Ele recebe esse nome porque a cada rodada do algoritmo, 256 00:16:01,200 --> 00:16:05,240 o maior objeto não classificado borbulha para o topo. 257 00:16:05,240 --> 00:16:09,000 Como todos os nossos algoritmos até agora, há método na loucura. 258 00:16:14,760 --> 00:16:16,640 Para ver como esse algoritmo funciona, 259 00:16:16,640 --> 00:16:19,120 vamos usá-lo para classificar oito objetos. 260 00:16:20,760 --> 00:16:24,720 Agora, o algoritmo de classificação por bolha diz para considerar os objetos em pares 261 00:16:24,720 --> 00:16:27,480 e troque-os se estiverem na ordem errada. 262 00:16:27,480 --> 00:16:31,840 Então, vamos começar por aqui e trabalhar até chegar ao topo. 263 00:16:31,840 --> 00:16:35,880 Então eu considero esses dois, eles estão na ordem errada, então eu os troco. 264 00:16:37,560 --> 00:16:40,000 Considere o próximo par, eles estão na ordem certa, 265 00:16:40,000 --> 00:16:42,280 então eu os deixo como estão. 266 00:16:42,280 --> 00:16:45,960 Considere este par, eles estão na ordem errada, então eu os troco. 267 00:16:48,920 --> 00:16:51,080 E continuamos fazendo isso. 268 00:16:58,160 --> 00:17:01,600 Agora, o algoritmo de classificação por bolha diz para voltar ao início 269 00:17:01,600 --> 00:17:05,760 e repita o processo indefinidamente até que os objetos estejam em ordem. 270 00:17:19,800 --> 00:17:24,120 O algoritmo para quando não há pares para trocar. 271 00:17:24,120 --> 00:17:27,880 Portanto, o algoritmo de classificação por bolha fez seu trabalho com sucesso. 272 00:17:27,880 --> 00:17:30,760 Agora tenho os objetos perfeitamente ordenados, 273 00:17:30,760 --> 00:17:32,640 de acordo com a altura ascendente. 274 00:17:34,160 --> 00:17:37,640 A classificação por bolha é elegantemente simples e direta. 275 00:17:37,640 --> 00:17:41,880 Mas se a escala da tarefa de classificação for enorme, por exemplo, organizar vastas áreas 276 00:17:41,880 --> 00:17:45,720 de dados, então pode haver algoritmos de classificação melhores para o trabalho. 277 00:17:50,800 --> 00:17:52,680 Este é John von Neumann, 278 00:17:52,680 --> 00:17:56,560 o gênio científico que ajudou a criar o computador moderno, 279 00:17:56,560 --> 00:17:58,760 teoria dos jogos, a bomba atômica 280 00:17:58,760 --> 00:18:02,200 e, ao que parece, inventou um algoritmo de classificação. 281 00:18:04,760 --> 00:18:08,080 Ele o criou para trabalhar nisso, um dos primeiros 282 00:18:08,080 --> 00:18:11,880 computadores eletrônicos, que ele ajudou a projetar. 283 00:18:11,880 --> 00:18:14,800 O algoritmo é chamado de classificação por mesclagem. 284 00:18:16,800 --> 00:18:21,200 O algoritmo de classificação por mesclagem funciona com base no princípio de dividir para conquistar. 285 00:18:21,200 --> 00:18:26,280 E consiste em duas partes. O primeiro bit é a parte divisória. 286 00:18:28,560 --> 00:18:31,920 Isso envolve dividir tudo em grupos menores. 287 00:18:35,240 --> 00:18:38,160 E agora vem a parte da conquista. 288 00:18:40,720 --> 00:18:43,640 Os grupos agora estão mesclados novamente. 289 00:18:43,640 --> 00:18:47,480 Mas ao mesclar os dois grupos, comparo os tamanhos dos objetos 290 00:18:47,480 --> 00:18:51,400 um par de cada vez para que o grupo mesclado seja classificado. 291 00:19:00,480 --> 00:19:03,240 Agora, o algoritmo de classificação por mesclagem pode ser bastante semelhante ao 292 00:19:03,240 --> 00:19:07,240 classificação de bolha, mas onde ela se destaca é com um tamanho maior 293 00:19:07,240 --> 00:19:10,280 número de objetos, é muito, muito mais rápido. 294 00:19:10,280 --> 00:19:15,520 Então, vamos ver como a classificação por mesclagem se compara em velocidade à classificação por bolha. 295 00:19:15,520 --> 00:19:18,040 É hora de uma batalha de algoritmos! 296 00:19:21,880 --> 00:19:26,000 Aqui temos a classificação por bolha na parte inferior e a classificação por mesclagem na parte superior. 297 00:19:26,000 --> 00:19:28,760 E nós os colocamos classificando 1.000 objetos. 298 00:19:28,760 --> 00:19:31,840 Agora, embora ambos produzam o mesmo resultado final, 299 00:19:31,840 --> 00:19:35,280 você já pode ver que a classificação por mesclagem está chegando lá muito mais rápido. 300 00:19:35,280 --> 00:19:38,760 E essa diferença no desempenho fica mais pronunciada 301 00:19:38,760 --> 00:19:41,120 mais objetos eles serão solicitados a classificar. 302 00:19:53,040 --> 00:19:55,200 RISOS 303 00:19:57,600 --> 00:19:59,560 Bem, é... 304 00:19:59,560 --> 00:20:02,920 - Me desculpe, talvez... - Não, não, não, não, não. 305 00:20:02,920 --> 00:20:05,000 Eu-eu acho... eu acho, er... 306 00:20:05,000 --> 00:20:08,400 Acho que o tipo bolha seria o caminho errado a seguir. 307 00:20:08,400 --> 00:20:10,160 RISOS 308 00:20:10,160 --> 00:20:11,680 APLAUSOS 309 00:20:12,720 --> 00:20:15,360 Vamos. Quem disse isso a ele? 310 00:20:22,480 --> 00:20:24,760 A classificação por mesclagem supera a classificação por bolha sem dúvida 311 00:20:24,760 --> 00:20:26,800 para classificar grandes quantidades de dados. 312 00:20:28,560 --> 00:20:31,200 Mas no mundo louco dos algoritmos, existem muitos, 313 00:20:31,200 --> 00:20:33,520 muitas maneiras diferentes de classificar. 314 00:20:36,000 --> 00:20:37,680 Na última contagem, 315 00:20:37,680 --> 00:20:41,160 havia mais de 20 tipos diferentes de algoritmos de classificação. 316 00:20:42,920 --> 00:20:46,800 Todos estranhamente alcançando o mesmo resultado, mas por meios diferentes. 317 00:20:58,240 --> 00:21:02,680 - Portanto, existe a classificação por bolha e a classificação por mesclagem. - Classificação de inserção. 318 00:21:02,680 --> 00:21:06,480 - Existe a classificação heap, existe a classificação rápida. - Timsort. 319 00:21:06,480 --> 00:21:07,840 Você tem uma espécie de gnomo. 320 00:21:07,840 --> 00:21:10,840 Existe o tipo pigeonhole, que também é chamado de tipo radix. 321 00:21:10,840 --> 00:21:13,440 Existe o bogosort, que pode nunca terminar. 322 00:21:19,400 --> 00:21:23,320 Não existe o melhor algoritmo de classificação. 323 00:21:23,320 --> 00:21:25,440 Cada um tem seus prós e contras. 324 00:21:26,640 --> 00:21:28,080 E qual deles se acostuma 325 00:21:28,080 --> 00:21:31,080 muitas vezes depende das especificidades do problema. 326 00:21:32,760 --> 00:21:36,640 Acho que a beleza de estudar algoritmos é tentar aspirar 327 00:21:36,640 --> 00:21:40,400 para soluções tão elegantes e eficientes quanto possível. 328 00:21:40,400 --> 00:21:44,640 Na verdade, acho que o tipo bolha é muito bonito. Eu gosto disso. 329 00:21:44,640 --> 00:21:46,320 A classificação de mesclagem é linda. 330 00:21:49,520 --> 00:21:51,840 Nós realmente não poderíamos viver sem eles. 331 00:21:51,840 --> 00:21:54,840 Algoritmos de classificação trazem ordem ao mundo. 332 00:22:05,240 --> 00:22:07,920 Até agora, vimos algoritmos lidarem com os pequenos 333 00:22:07,920 --> 00:22:11,280 problemas de dimensionamento dos azulejos do banheiro e classificação dos dados. 334 00:22:12,920 --> 00:22:16,040 Mas quão bem eles lidam com o mundo confuso do amor? 335 00:22:18,080 --> 00:22:20,880 O namoro online é muito popular hoje em dia. 336 00:22:20,880 --> 00:22:23,640 Na verdade, um inquérito sugere que mais de um terço 337 00:22:23,640 --> 00:22:26,400 dos casamentos recentes começaram online. 338 00:22:27,400 --> 00:22:30,800 A forma como esses sites de namoro funcionam é que eles usam algo chamado 339 00:22:30,800 --> 00:22:33,000 um algoritmo de correspondência. 340 00:22:33,000 --> 00:22:36,200 Eles pesquisam nos perfis, tentam combinar as pessoas de acordo 341 00:22:36,200 --> 00:22:40,320 aos seus gostos e desgostos, traços de personalidade e assim por diante. 342 00:22:40,320 --> 00:22:43,200 Na verdade, os algoritmos parecem ser melhores que os humanos. 343 00:22:43,200 --> 00:22:46,480 Porque pesquisas recentes mostraram que aqueles que se encontram on-line 344 00:22:46,480 --> 00:22:49,160 tendem a ser mais felizes e a ter casamentos mais longos. 345 00:22:52,360 --> 00:22:56,640 Pedirei que você receba seus prêmios de Sua Majestade o Rei. 346 00:22:56,640 --> 00:23:01,080 Na verdade, os algoritmos de correspondência têm muito do que se gabar. 347 00:23:01,080 --> 00:23:05,800 Porque em 2012, pela primeira vez, foi atribuído um Prémio Nobel 348 00:23:05,800 --> 00:23:07,840 por causa de um algoritmo. 349 00:23:07,840 --> 00:23:11,280 Um algoritmo de correspondência criado pelo falecido David Gale 350 00:23:11,280 --> 00:23:13,480 e o matemático Lloyd Shapley, 351 00:23:13,480 --> 00:23:16,240 visto aqui recebendo sua parte do prêmio. 352 00:23:20,040 --> 00:23:23,720 A história começa na década de 1960, quando Gale e Shapley queriam 353 00:23:23,720 --> 00:23:27,840 resolver um problema relacionado com admissões em faculdades. 354 00:23:27,840 --> 00:23:31,880 Como combinar alunos com faculdades para que todos tenham uma vaga. 355 00:23:32,880 --> 00:23:35,400 Mas, o mais importante, estava feliz, mesmo que 356 00:23:35,400 --> 00:23:37,480 eles não tiveram sua primeira escolha. 357 00:23:40,480 --> 00:23:44,160 Eles chamaram isso de problema do casamento estável. 358 00:23:44,160 --> 00:23:46,680 O problema do casamento estável é assim. 359 00:23:46,680 --> 00:23:49,120 Suponha que você tenha quatro mulheres e quatro homens 360 00:23:49,120 --> 00:23:51,000 e eles querem se casar. 361 00:23:51,000 --> 00:23:54,000 Agora, eles se classificaram de acordo com suas preferências. 362 00:23:54,000 --> 00:23:55,880 Então, por exemplo, a Rainha de Copas aqui, 363 00:23:55,880 --> 00:23:57,960 a primeira escolha é o Rei de Paus. 364 00:23:57,960 --> 00:24:00,040 Segunda escolha, Rei de Ouros, 365 00:24:00,040 --> 00:24:02,840 e sua última escolha é o Rei de Copas. 366 00:24:02,840 --> 00:24:06,080 Então o desafio aqui é bancar o Cupido e formar pares de reis 367 00:24:06,080 --> 00:24:09,920 e rainhas para que cada uma tenha um parceiro, mas, mais importante, 368 00:24:09,920 --> 00:24:12,520 para que os casamentos sejam estáveis. 369 00:24:12,520 --> 00:24:15,640 Um casamento estável significa que os reis e rainhas não 370 00:24:15,640 --> 00:24:20,640 necessariamente obtêm a primeira escolha, mas obtêm o melhor em oferta. 371 00:24:20,640 --> 00:24:25,240 Por exemplo, se eu emparelhasse o Rei de Copas e a Rainha de Copas 372 00:24:25,240 --> 00:24:28,240 e o Rei de Espadas e a Dama de Espadas, 373 00:24:28,240 --> 00:24:31,040 este seria um casamento instável. 374 00:24:31,040 --> 00:24:34,480 Porque o Rei de Espadas não gosta muito da Dama de Espadas. 375 00:24:34,480 --> 00:24:36,640 Ele preferiria a Rainha de Copas. 376 00:24:38,120 --> 00:24:40,040 A Rainha de Copas, por sua vez, 377 00:24:40,040 --> 00:24:41,960 realmente não gosta do Rei de Copas. 378 00:24:41,960 --> 00:24:44,840 Ela preferiria o Rei de Espadas. 379 00:24:44,840 --> 00:24:48,120 Então esses dois vão fugir juntos neste par. 380 00:24:51,960 --> 00:24:56,480 Onde há um problema, há um algoritmo não muito atrás. 381 00:24:56,480 --> 00:24:59,160 Em 1962, Gale e Shapley criaram 382 00:24:59,160 --> 00:25:02,760 seu algoritmo vencedor do Prêmio Nobel. 383 00:25:02,760 --> 00:25:09,560 Uma receita passo a passo que sempre encontra casamentos perfeitamente estáveis. 384 00:25:09,560 --> 00:25:11,240 Então, na primeira rodada do algoritmo, 385 00:25:11,240 --> 00:25:14,440 todas as rainhas fizeram propostas aos seus reis de primeira escolha. 386 00:25:14,440 --> 00:25:18,720 Portanto, a primeira escolha da Dama de Espadas é o Rei de Espadas. 387 00:25:18,720 --> 00:25:21,200 Ela pede o Rei de Espadas em casamento. 388 00:25:21,200 --> 00:25:24,360 A primeira escolha da Rainha de Copas é o Rei de Paus, 389 00:25:24,360 --> 00:25:26,800 então ela pede em casamento ao Rei de Paus. 390 00:25:26,800 --> 00:25:30,360 A primeira escolha da Rainha de Ouros é o Rei de Espadas. 391 00:25:30,360 --> 00:25:33,320 E a primeira escolha da Rainha de Paus também é o Rei de Espadas. 392 00:25:33,320 --> 00:25:36,600 Portanto, o Rei de Espadas parece ser o Darcy desta corte real. 393 00:25:37,800 --> 00:25:40,560 Agora, o Rei de Espadas tem três propostas. 394 00:25:41,720 --> 00:25:44,840 Então ele escolhe sua rainha mais popular, 395 00:25:44,840 --> 00:25:48,640 que na verdade é a Rainha de Ouros, e rejeita as outras duas. 396 00:25:51,440 --> 00:25:55,600 Portanto, temos dois compromissos provisórios, duas rejeições. 397 00:25:55,600 --> 00:25:59,280 Removemos agora as primeiras escolhas da rainha rejeitada. 398 00:25:59,280 --> 00:26:01,040 E é hora da segunda rodada. 399 00:26:02,480 --> 00:26:06,960 Então a Dama de Espadas vai propor casamento ao Rei de Ouros. 400 00:26:06,960 --> 00:26:10,160 E a Rainha de Paus pede em casamento ao Rei de Paus. 401 00:26:11,560 --> 00:26:14,240 Mas agora o Rei de Paus tem duas propostas 402 00:26:14,240 --> 00:26:17,440 e na verdade prefere a Rainha de Paus. 403 00:26:17,440 --> 00:26:20,280 Então ele rejeita a Rainha de Copas, seu provisório 404 00:26:20,280 --> 00:26:22,920 engajamento na primeira rodada do algoritmo, 405 00:26:22,920 --> 00:26:24,440 e temos que começar de novo. 406 00:26:26,000 --> 00:26:28,080 Em cada rodada, as rainhas rejeitadas 407 00:26:28,080 --> 00:26:31,360 propor ao próximo rei de sua lista. 408 00:26:31,360 --> 00:26:34,480 E os reis sempre buscam a melhor oferta que recebem. 409 00:26:35,680 --> 00:26:40,000 Nesta rodada do algoritmo, ela propõe ao Rei de Copas 410 00:26:40,000 --> 00:26:44,040 e finalmente, todos formaram pares com uma única rainha e rei 411 00:26:44,040 --> 00:26:45,960 e todos os casamentos são estáveis. 412 00:26:49,120 --> 00:26:53,440 O algoritmo Gale-Shapley é agora usado em todo o mundo. 413 00:26:53,440 --> 00:26:56,840 Na Dinamarca, para adaptar as crianças às creches. 414 00:26:56,840 --> 00:27:00,040 Na Hungria, para combinar os alunos com as escolas. 415 00:27:00,040 --> 00:27:03,440 Em Nova York, para alocar rabinos nas sinagogas. 416 00:27:03,440 --> 00:27:07,360 E na China, Alemanha e Espanha, para adequar os estudantes às universidades. 417 00:27:10,480 --> 00:27:13,560 Enquanto no Reino Unido, levou ao desenvolvimento 418 00:27:13,560 --> 00:27:18,440 de um algoritmo de correspondência que, para algumas pessoas, salvou suas vidas. 419 00:27:23,040 --> 00:27:26,800 Aos 20 anos, Seraya, no sul de Londres, foi diagnosticada 420 00:27:26,800 --> 00:27:31,120 com doença renal crônica e disse que precisava de um transplante. 421 00:27:32,880 --> 00:27:37,000 Fiquei em diálise por 18 meses e muito mal. 422 00:27:37,000 --> 00:27:40,240 Eu não pude ir trabalhar. Eu não tinha vida social. 423 00:27:40,240 --> 00:27:44,200 Era literalmente hospitalizado três vezes por semana para tratamento e para casa. 424 00:27:45,440 --> 00:27:47,880 Um amigo próximo estava disposto a doar, 425 00:27:47,880 --> 00:27:50,880 mas seus tipos de tecidos não eram compatíveis. 426 00:27:53,480 --> 00:27:55,840 Em St Albans, Tamir estava gravemente doente 427 00:27:55,840 --> 00:27:58,840 e sua esposa, Lyndsey, queriam doar. 428 00:27:58,840 --> 00:28:00,560 Mas eles tiveram o mesmo problema. 429 00:28:02,000 --> 00:28:04,760 Passamos por todos os exames de sangue e todos os exames 430 00:28:04,760 --> 00:28:08,040 e descobrimos que éramos grupos sanguíneos incompatíveis. 431 00:28:10,320 --> 00:28:13,080 Muitas vezes, os pacientes renais que têm a sorte 432 00:28:13,080 --> 00:28:16,080 fazer com que um possível doador descubra que há uma incompatibilidade 433 00:28:16,080 --> 00:28:18,920 entre o grupo sanguíneo ou tipo de tecido do doador. 434 00:28:20,720 --> 00:28:26,280 Mas desde 2007, o NHS tem utilizado um algoritmo de correspondência especial 435 00:28:26,280 --> 00:28:29,160 para encontrar possíveis correspondências para doadores dispostos 436 00:28:29,160 --> 00:28:31,480 para pacientes renais em todo o Reino Unido. 437 00:28:35,360 --> 00:28:37,640 Quando analisamos esse problema pela primeira vez, 438 00:28:37,640 --> 00:28:41,320 nós realmente subestimamos a complexidade. 439 00:28:41,320 --> 00:28:46,360 E originalmente, começamos com trocas entre dois pares. 440 00:28:46,360 --> 00:28:48,120 Então foi muito simples, 441 00:28:48,120 --> 00:28:53,040 mas logo ficou óbvio que precisávamos de algo muito mais complexo. 442 00:28:56,920 --> 00:29:00,000 Entrei em contato com Rachel Johnson no NHS 443 00:29:00,000 --> 00:29:02,720 e então nos envolvemos nessa fase em sermos capazes de projetar 444 00:29:02,720 --> 00:29:05,560 algoritmos que permitiriam não apenas trocas entre pares, 445 00:29:05,560 --> 00:29:08,120 mas também trocas entre três casais. 446 00:29:10,080 --> 00:29:13,080 O algoritmo considera vários cenários. 447 00:29:13,080 --> 00:29:15,400 O mais simples é uma troca bidirecional 448 00:29:15,400 --> 00:29:18,360 com dois casais trocando rins. 449 00:29:21,560 --> 00:29:23,840 Mais complicado é uma troca de três vias, 450 00:29:23,840 --> 00:29:26,720 onde os rins são transmitidos em um ciclo. 451 00:29:29,960 --> 00:29:34,960 Existem 200 pacientes em cada uma de nossas execuções correspondentes. 452 00:29:34,960 --> 00:29:38,960 Precisamos procurar todos os transplantes possíveis. 453 00:29:40,200 --> 00:29:42,440 E é surpreendente quantos existem. 454 00:29:42,440 --> 00:29:44,440 Existem literalmente, você sabe, centenas, 455 00:29:44,440 --> 00:29:47,040 às vezes milhares de possibilidades. 456 00:29:47,040 --> 00:29:51,400 É algo que simplesmente não poderia ser alcançado sem o algoritmo. 457 00:29:53,120 --> 00:29:57,120 Um dia, Seraya recebeu a ligação informando que uma correspondência havia sido encontrada 458 00:29:57,120 --> 00:30:02,200 A 640 quilômetros de distância com Linda, uma doadora que mora em Bowness, perto de Edimburgo. 459 00:30:03,720 --> 00:30:06,760 O pai do meu marido precisava de um novo rim. 460 00:30:06,760 --> 00:30:11,200 Ele estava doente há algum tempo. E eu não era um par perfeito. 461 00:30:11,200 --> 00:30:17,000 E então recebi um telefonema e tudo começou a partir daí. 462 00:30:19,120 --> 00:30:20,920 Recebemos o telefonema inicial dizendo 463 00:30:20,920 --> 00:30:23,520 tínhamos sido combinados no grupo de três. 464 00:30:23,520 --> 00:30:26,560 Você só está nervoso porque isso não vai acontecer 465 00:30:26,560 --> 00:30:28,240 porque sua vida depende disso. 466 00:30:29,960 --> 00:30:31,640 Para os casais correspondentes, 467 00:30:31,640 --> 00:30:35,080 todas as operações tinham que acontecer simultaneamente. 468 00:30:35,080 --> 00:30:38,280 Foi um grande desafio logístico. 469 00:30:38,280 --> 00:30:41,360 Quando meu doador foi ao teatro, eles ligaram para verificar 470 00:30:41,360 --> 00:30:44,600 que meu doador também estava em Newcastle indo ao teatro. 471 00:30:44,600 --> 00:30:46,960 E os dois conseguiram exatamente ao mesmo tempo. 472 00:30:46,960 --> 00:30:49,400 E eles fazem a ligação e os rins saem. 473 00:30:49,400 --> 00:30:51,160 Acho que eles foram de moto. 474 00:30:51,160 --> 00:30:53,120 Disseram-nos que eles poderiam ir de helicóptero, 475 00:30:53,120 --> 00:30:56,680 então pensei que pelo menos uma parte de mim poderia estar em um helicóptero, 476 00:30:56,680 --> 00:30:58,960 mas não, foi de moto. 477 00:31:02,880 --> 00:31:06,200 E finalmente foi adiante, felizmente, em dezembro. 478 00:31:06,200 --> 00:31:09,160 - O melhor presente de Natal. - Hum! 479 00:31:09,160 --> 00:31:12,440 Pessoalmente, imaginei que fossem os médicos por trás 480 00:31:12,440 --> 00:31:14,880 combinando pessoas desta lista. 481 00:31:14,880 --> 00:31:17,640 Então, sim, é um pouco estranho 482 00:31:17,640 --> 00:31:20,240 que tudo se resume à matemática no final do dia. 483 00:31:20,240 --> 00:31:23,720 É um ótimo esquema e ainda é bastante recente. 484 00:31:23,720 --> 00:31:27,120 E muitos anos atrás, eu não teria tido essa chance. 485 00:31:27,120 --> 00:31:31,480 Sinto muita gratidão à Linda e também ao algoritmo. 486 00:31:31,480 --> 00:31:33,400 Então, sim, estou muito grato. 487 00:31:34,680 --> 00:31:39,760 Até agora, mais de 400 pacientes já beneficiaram do regime do SNS 488 00:31:39,760 --> 00:31:42,520 e seu algoritmo de correspondência especial. 489 00:31:42,520 --> 00:31:44,840 Foi só quando vimos artigos na mídia 490 00:31:44,840 --> 00:31:47,160 e começamos a pensar: "Ah, espere, 491 00:31:47,160 --> 00:31:49,480 "essa pessoa pode realmente ter tido aquela partida 492 00:31:49,480 --> 00:31:53,080 "por meio da troca de pares da execução de outubro" e assim por diante, 493 00:31:53,080 --> 00:31:55,320 que você realmente comece a ver as histórias 494 00:31:55,320 --> 00:31:57,200 que estão por trás dos dados anônimos. 495 00:31:57,200 --> 00:32:00,560 É muito engraçado porque David está sempre muito preocupado 496 00:32:00,560 --> 00:32:03,400 que o algoritmo levará muito tempo para ser executado. 497 00:32:03,400 --> 00:32:07,280 E, você sabe, já se passaram 30 minutos e ele fica preocupado. 498 00:32:07,280 --> 00:32:10,440 Mas na verdade, 30 minutos, você sabe, para nós, 499 00:32:10,440 --> 00:32:14,080 é incrível que ele possa fazer tudo isso em 30 minutos. 500 00:32:25,000 --> 00:32:29,360 Até agora, vimos como os algoritmos são capazes de feitos incríveis. 501 00:32:30,440 --> 00:32:33,520 Da resolução de problemas matemáticos abstratos 502 00:32:33,520 --> 00:32:37,320 para nos ajudar a encontrar coisas na World Wide Web. 503 00:32:37,320 --> 00:32:41,240 E o principal para todos esses algoritmos é a velocidade. 504 00:32:41,240 --> 00:32:44,480 Portanto, a característica importante de um bom algoritmo é primeiro 505 00:32:44,480 --> 00:32:47,440 que é melhor que esteja correto, mas quando você souber que está correto, 506 00:32:47,440 --> 00:32:49,400 também é importante que seja executado rapidamente. 507 00:32:49,400 --> 00:32:52,600 Não adianta ter um algoritmo que demora mais 508 00:32:52,600 --> 00:32:57,000 do que sua vida inteira para correr se você quiser o resultado amanhã. 509 00:32:58,320 --> 00:33:02,680 Este algoritmo de detecção de rosto é um exemplo de algoritmo eficiente. 510 00:33:02,680 --> 00:33:05,840 Por ser eficiente, é capaz de funcionar em tempo real. 511 00:33:05,840 --> 00:33:07,720 E é isso que o torna útil. 512 00:33:09,640 --> 00:33:14,160 Mas, assim como na vida real, alguns problemas são mais difíceis que outros. 513 00:33:14,160 --> 00:33:17,480 De vez em quando, os algoritmos encontram seu par. 514 00:33:19,200 --> 00:33:21,960 Acho que o equívoco mais comum sobre algoritmos 515 00:33:21,960 --> 00:33:24,280 é que os algoritmos podem fazer qualquer coisa. 516 00:33:24,280 --> 00:33:27,240 Acho que as pessoas realmente não sabem sobre os limites. 517 00:33:27,240 --> 00:33:30,760 Alguns problemas simplesmente não podem ser resolvidos por algoritmos eficientes. 518 00:33:32,640 --> 00:33:36,800 Existem alguns lugares onde algoritmos eficientes não podem chegar. 519 00:33:36,800 --> 00:33:40,000 Linhas na areia que não podem ser cruzadas. 520 00:33:40,000 --> 00:33:43,240 O problema é saber quais problemas eles podem resolver 521 00:33:43,240 --> 00:33:44,680 e quais eles não podem. 522 00:33:48,040 --> 00:33:51,320 Pegue este Cubo de Rubik e imagine o desafio mais geral 523 00:33:51,320 --> 00:33:54,000 de tentar resolver um cubo de dimensões arbitrárias. 524 00:33:54,000 --> 00:33:57,040 Então, por exemplo, com 50 quadrados em cada lado. 525 00:33:57,040 --> 00:33:58,520 Agora, você pode esperar isso 526 00:33:58,520 --> 00:34:01,600 ser um dos problemas realmente terrivelmente difíceis, 527 00:34:01,600 --> 00:34:03,960 mas, na verdade, pertence ao campo fácil. 528 00:34:03,960 --> 00:34:08,000 Conhecemos um algoritmo que pode resolver o Cubo de Rubik geral 529 00:34:08,000 --> 00:34:09,800 em um período de tempo razoável. 530 00:34:13,320 --> 00:34:14,680 Embora pareça difícil, 531 00:34:14,680 --> 00:34:17,920 esse problema pode ser resolvido por algoritmos eficientes. 532 00:34:22,800 --> 00:34:25,280 No entanto, aqui está um que definitivamente não pode. 533 00:34:27,400 --> 00:34:30,320 Imagine que você tem um quadro de rascunhos de tamanho arbitrário 534 00:34:30,320 --> 00:34:32,800 e um arranjo de peças no tabuleiro. 535 00:34:32,800 --> 00:34:34,360 O desafio é trabalhar 536 00:34:34,360 --> 00:34:38,240 se as brancas podem forçar uma vitória nesta posição. 537 00:34:38,240 --> 00:34:40,120 Agora, draft é um jogo bem fácil, 538 00:34:40,120 --> 00:34:42,400 mas foi matematicamente comprovado 539 00:34:42,400 --> 00:34:46,640 que não há algoritmo que possa resolver este problema de forma eficiente. 540 00:34:46,640 --> 00:34:49,040 É um problema inerentemente difícil. 541 00:34:51,160 --> 00:34:55,600 A única maneira de resolver esse quebra-cabeça é através de um trabalho árduo - 542 00:34:55,600 --> 00:34:58,320 trabalhando em todos os milhões de possibilidades. 543 00:35:00,080 --> 00:35:04,840 Portanto, este problema está firmemente fora do alcance de algoritmos eficientes. 544 00:35:04,840 --> 00:35:06,520 Não pode ser resolvido rapidamente. 545 00:35:10,240 --> 00:35:14,600 Mas, para alguns problemas, a sua dificuldade não é clara. 546 00:35:14,600 --> 00:35:19,080 Este é um sudoku grande. Tem 625 quadrados. 547 00:35:20,320 --> 00:35:24,400 Uma das coisas boas do sudoku é que depois de encontrar uma solução, 548 00:35:24,400 --> 00:35:28,040 é relativamente simples verificar se está certo ou não. 549 00:35:28,040 --> 00:35:30,360 E isso é verdade, por maior que seja o quebra-cabeça. 550 00:35:32,360 --> 00:35:34,800 Neste caso, só preciso verificar cada linha, 551 00:35:34,800 --> 00:35:38,280 coluna e bloco não apresentam um número duas vezes. 552 00:35:38,280 --> 00:35:42,240 O Sudoku pertence a uma categoria muito especial de problemas 553 00:35:42,240 --> 00:35:44,840 que todos compartilham essa característica. 554 00:35:44,840 --> 00:35:48,840 Depois de encontrar uma solução, é sempre fácil verificá-la. 555 00:35:49,880 --> 00:35:53,160 O mistério é se existe um algoritmo eficiente 556 00:35:53,160 --> 00:35:55,520 para encontrar a solução em primeiro lugar. 557 00:35:58,360 --> 00:36:02,520 E o sudoku não está sozinho. Existem muitos problemas como este. 558 00:36:02,520 --> 00:36:05,040 O mais intensamente estudado de todos 559 00:36:05,040 --> 00:36:08,480 é conhecido como problema do caixeiro viajante. 560 00:36:13,360 --> 00:36:16,920 Um caixeiro-viajante viaja de porta em porta, de cidade em cidade, 561 00:36:16,920 --> 00:36:20,480 vendendo de tudo, desde escovas e aspiradores até vidros duplos. 562 00:36:22,520 --> 00:36:25,000 Parece um trabalho simples. 563 00:36:25,000 --> 00:36:28,880 Mas todos os caixeiros-viajantes enfrentam a mesma questão. 564 00:36:28,880 --> 00:36:31,560 Qual é o caminho mais curto a seguir? 565 00:36:33,520 --> 00:36:37,400 Este problema é tão importante que o Clay Mathematics Institute 566 00:36:37,400 --> 00:36:42,120 ofereceu 1 milhão para quem conseguir encontrar um algoritmo eficiente, 567 00:36:42,120 --> 00:36:44,520 ou provar que nada existe. 568 00:36:46,400 --> 00:36:49,000 O problema do caixeiro viajante é assim. 569 00:36:49,000 --> 00:36:50,520 Imagine que você é um vendedor 570 00:36:50,520 --> 00:36:55,120 e você deve visitar uma lista de cidades representadas pelos pontos vermelhos. 571 00:36:55,120 --> 00:36:57,640 O desafio é encontrar o caminho mais curto 572 00:36:57,640 --> 00:37:02,040 então você visita cada cidade uma vez antes de retornar ao ponto de partida. 573 00:37:02,040 --> 00:37:04,520 Agora, você pode imaginar que a melhor coisa é 574 00:37:04,520 --> 00:37:07,520 considerar apenas todas as rotas, assim. 575 00:37:13,960 --> 00:37:18,560 O método de verificação de todas as possibilidades é um tipo de algoritmo. 576 00:37:18,560 --> 00:37:20,440 E para três cidades, funciona bem 577 00:37:20,440 --> 00:37:23,640 porque existem apenas três rotas possíveis para verificar. 578 00:37:27,080 --> 00:37:30,200 Mas e se adicionarmos mais duas cidades à lista? 579 00:37:32,920 --> 00:37:36,360 Com cinco cidades, existem 60 rotas diferentes possíveis. 580 00:37:39,160 --> 00:37:44,040 E se adicionarmos outra cidade, existem 360 rotas possíveis. 581 00:37:44,040 --> 00:37:49,320 E para dez cidades, existem mais de 1,8 milhões de rotas possíveis. 582 00:37:49,320 --> 00:37:51,600 Se nosso algoritmo passasse por eles, 583 00:37:51,600 --> 00:37:54,720 verificando tudo isso a uma taxa de dez por segundo, 584 00:37:54,720 --> 00:37:58,320 levaria dois dias até encontrar o mais curto. 585 00:37:58,320 --> 00:38:01,720 Então você pode ver um método para tentar todas as diferentes possibilidades, 586 00:38:01,720 --> 00:38:06,440 um tipo de algoritmo de força bruta, se preferir, é simplesmente impraticável. 587 00:38:07,720 --> 00:38:10,880 Se alguém encontrasse um algoritmo rápido para o problema do caixeiro viajante, 588 00:38:10,880 --> 00:38:12,280 seria extremamente significativo. 589 00:38:12,280 --> 00:38:15,240 Se um dos meus alunos criasse um algoritmo eficiente 590 00:38:15,240 --> 00:38:17,320 para o problema do caixeiro viajante, 591 00:38:17,320 --> 00:38:20,280 Eu faria com que ele me explicasse, 592 00:38:20,280 --> 00:38:23,200 Eu o mataria e então iria reivindicar 593 00:38:23,200 --> 00:38:25,720 o prêmio Clay, 1 milhão. 594 00:38:25,720 --> 00:38:28,360 Mas acho que meus alunos estão seguros. 595 00:38:29,680 --> 00:38:32,680 O problema surge em muitas áreas. 596 00:38:32,680 --> 00:38:35,000 Da soldagem de placas de circuito... 597 00:38:37,360 --> 00:38:40,680 ..para planejar as rotas para entregas em supermercados. 598 00:38:40,680 --> 00:38:45,320 Mas será que o problema do caixeiro viajante já foi secretamente resolvido? 599 00:38:49,960 --> 00:38:54,080 Uma equipe de cientistas trabalhando na Rothamsted Research em Harpenden 600 00:38:54,080 --> 00:38:57,520 recorremos à natureza para ver se ela encontrou a resposta. 601 00:39:03,200 --> 00:39:06,160 Eles estão realizando um experimento elaborado para estudar 602 00:39:06,160 --> 00:39:10,320 como o problema do caixeiro viajante é resolvido pela abelha. 603 00:39:13,480 --> 00:39:17,680 As abelhas precisam procurar néctar para abastecer sua colmeia. 604 00:39:17,680 --> 00:39:19,920 E então eles têm que visitar 605 00:39:19,920 --> 00:39:22,520 possivelmente centenas de flores em cada viagem. 606 00:39:22,520 --> 00:39:25,240 O que eles querem fazer é encontrar uma maneira eficiente 607 00:39:25,240 --> 00:39:28,040 passar entre todas essas flores que eles visitam. 608 00:39:31,360 --> 00:39:35,680 A humilde abelha enfrenta seu próprio problema de caixeiro-viajante. 609 00:39:35,680 --> 00:39:38,360 As flores são como as cidades. 610 00:39:38,360 --> 00:39:41,480 E a abelha é o caixeiro viajante. 611 00:39:41,480 --> 00:39:45,600 Uma abelha sai em busca de alimento muitas e muitas vezes todos os dias. 612 00:39:45,600 --> 00:39:47,360 Então, ao longo de um dia, 613 00:39:47,360 --> 00:39:51,680 realmente ajuda seguir o caminho mais eficiente possível. 614 00:39:51,680 --> 00:39:53,920 Então, o que estamos fazendo é tentar descobrir 615 00:39:53,920 --> 00:39:58,000 exatamente quais regras eles estão usando para restringir as possibilidades. 616 00:40:00,480 --> 00:40:04,160 Joe preparou cinco alimentadores que fazem o papel de flores. 617 00:40:05,560 --> 00:40:10,200 Cada alimentador tem néctar suficiente para garantir que a abelha visite todos os cinco 618 00:40:10,200 --> 00:40:12,360 para dar-lhe um estômago cheio de mel. 619 00:40:13,560 --> 00:40:16,280 E como você realmente sabe para onde isso está indo? 620 00:40:16,280 --> 00:40:18,960 Para isso, estamos utilizando um radar harmônico. 621 00:40:18,960 --> 00:40:22,280 Então, enquanto isso gira e gira, ele emite um sinal de radar. 622 00:40:22,280 --> 00:40:25,200 E colocamos uma pequena antena na parte de trás da abelha, 623 00:40:25,200 --> 00:40:27,880 que então reflete o sinal do radar. 624 00:40:27,880 --> 00:40:31,200 E isso nos permite ver exatamente para onde a abelha foi 625 00:40:31,200 --> 00:40:32,800 enquanto ela se move pelo campo. 626 00:40:34,240 --> 00:40:38,000 Então, como a abelha resolve o problema do caixeiro viajante? 627 00:40:38,000 --> 00:40:40,120 OK, estamos ligando agora. 628 00:40:47,080 --> 00:40:51,600 Com cinco alimentadores, há um total de 60 rotas possíveis. 629 00:40:51,600 --> 00:40:54,480 O mais curto fica ao redor da borda externa. 630 00:40:58,040 --> 00:41:02,520 Este mapa de calor mostra o caminho percorrido por uma única abelha. 631 00:41:02,520 --> 00:41:06,240 A princípio, basta descobrir as posições dos alimentadores. 632 00:41:07,920 --> 00:41:12,360 Então a abelha parece mudar metodicamente diferentes partes da rota 633 00:41:12,360 --> 00:41:14,680 para ver se pode torná-lo mais curto. 634 00:41:16,920 --> 00:41:20,760 Em 20 viagens, ele está definido como uma rota eficiente. 635 00:41:26,480 --> 00:41:29,840 Este caminho nem sempre é o mais curto, 636 00:41:29,840 --> 00:41:31,760 mas, para a abelha, é bom o suficiente. 637 00:41:36,440 --> 00:41:40,040 É incrível que, depois de algumas tentativas, eles tenham conseguido 638 00:41:40,040 --> 00:41:44,040 para algo que seja eficiente o suficiente para que eles possam procurar alimentos. 639 00:41:44,040 --> 00:41:47,920 Sim, está certo. Eles não podem passar dias ou mesmo, você sabe, 640 00:41:47,920 --> 00:41:50,560 pode levar meses ou anos para tentar todas as possibilidades. 641 00:41:50,560 --> 00:41:52,920 Então eles têm que encontrar uma rota muito rapidamente 642 00:41:52,920 --> 00:41:55,680 que eles podem fazer de novo e de novo e de novo 643 00:41:55,680 --> 00:41:59,800 - para fornecer alimentos de forma eficiente. - Fantástico. 644 00:41:59,800 --> 00:42:01,960 Acho que a abelha se tornou meu inseto favorito agora. 645 00:42:01,960 --> 00:42:05,520 - É obviamente um matemático de coração. - Absolutamente. 646 00:42:06,920 --> 00:42:11,640 Sejamos claros. As abelhas não estão prestes a receber 1 milhão. 647 00:42:11,640 --> 00:42:15,120 Eles não resolveram milagrosamente o problema do caixeiro viajante 648 00:42:15,120 --> 00:42:18,080 porque nem sempre encontram o caminho mais curto. 649 00:42:19,400 --> 00:42:21,760 Mas o algoritmo deles é uma abordagem inteligente. 650 00:42:21,760 --> 00:42:25,080 Em matemática, isso é conhecido como heurística. 651 00:42:25,080 --> 00:42:29,320 Algoritmos que são eficientes, que não encontram a solução perfeita, 652 00:42:29,320 --> 00:42:31,080 mas chegue o mais perto que puder. 653 00:42:44,520 --> 00:42:46,720 A mesma abordagem heurística 654 00:42:46,720 --> 00:42:49,960 foi usado para desenvolver um algoritmo para o aeroporto de Heathrow. 655 00:42:51,400 --> 00:42:54,040 EXPEDIDOR: 'Livro para decolagem...' 656 00:42:54,040 --> 00:42:57,880 Heathrow realiza mais de 1.300 voos por dia. 657 00:42:57,880 --> 00:43:00,000 É o aeroporto mais movimentado da Europa. 658 00:43:00,000 --> 00:43:04,640 '..430 liberado para decolagem. Vento de superfície de 247 graus a três nós. 659 00:43:12,840 --> 00:43:15,120 O desafio do controle de tráfego aéreo 660 00:43:15,120 --> 00:43:18,640 é maximizar o número de aeronaves partindo a cada hora 661 00:43:18,640 --> 00:43:22,800 e garantir que o aeroporto opere de forma eficiente e segura. 662 00:43:22,800 --> 00:43:29,400 '..atrás do British Airways 747, alinhe 27 logo atrás.' 663 00:43:29,400 --> 00:43:33,520 Uma das principais decisões é a ordem de decolagem. 664 00:43:33,520 --> 00:43:36,680 No momento estamos partindo de um grupo de aeronaves médias, 665 00:43:36,680 --> 00:43:39,680 que serão separados com um minuto de intervalo. 666 00:43:39,680 --> 00:43:43,400 Atrás dele, então, você pode ver um 747, que é uma aeronave grande. 667 00:43:44,800 --> 00:43:48,200 Aeronaves médias precisam ser separadas da turbulência 668 00:43:48,200 --> 00:43:50,360 produzido por aeronaves maiores. 669 00:43:50,360 --> 00:43:52,720 Portanto, a ordem dos tamanhos é crucial. 670 00:43:53,800 --> 00:43:56,120 A sequência ideal para a decolagem envolve 671 00:43:56,120 --> 00:43:58,840 realmente bloqueando grupos de aeronaves. 672 00:43:58,840 --> 00:44:01,080 Então você quer que aeronaves grandes sejam agrupadas, 673 00:44:01,080 --> 00:44:03,440 aeronaves médias a serem agrupadas. 674 00:44:03,440 --> 00:44:05,240 E isso permite a separação 675 00:44:05,240 --> 00:44:07,640 entre essas aeronaves seja minimizada. 676 00:44:10,640 --> 00:44:14,160 O outro fator que precisa ser considerado ao planejar a decolagem 677 00:44:14,160 --> 00:44:16,040 é para onde os aviões estão indo. 678 00:44:19,920 --> 00:44:22,320 Queremos que um vá para o norte, outro para o sul, 679 00:44:22,320 --> 00:44:24,360 o próximo vai para o norte, depois para o sul. 680 00:44:24,360 --> 00:44:29,040 Se todas as aeronaves estivessem indo na mesma direção, a separação seria muito maior 681 00:44:29,040 --> 00:44:31,560 e não usaríamos as pistas com tanta eficiência. 682 00:44:31,560 --> 00:44:34,600 Todos os controladores estão sentados nas torres de controle pensando: 683 00:44:34,600 --> 00:44:37,880 “Tenho todas essas aeronaves indo para o norte, todas indo para o sul. 684 00:44:37,880 --> 00:44:39,640 "Eu tenho estes que são grandes, 685 00:44:39,640 --> 00:44:42,200 "então quero tentar agrupar todos os grandes 686 00:44:42,200 --> 00:44:44,600 "então não preciso passar de um grande para um pequeno." 687 00:44:44,600 --> 00:44:48,000 E é um problema muito complexo de resolver na cabeça deles. 688 00:44:48,000 --> 00:44:50,440 '..906 novembro...' 689 00:44:50,440 --> 00:44:54,280 Em 2013, um algoritmo se juntou à equipe. 690 00:44:54,280 --> 00:44:58,240 Sua função é prever a ordem mais provável de decolagem 691 00:44:58,240 --> 00:45:00,400 e aconselhar o controle de tráfego aéreo 692 00:45:00,400 --> 00:45:03,240 quando a aeronave deve recuar dos portões. 693 00:45:03,240 --> 00:45:06,240 Fazer isso envolve nada menos que simular 694 00:45:06,240 --> 00:45:09,480 toda a operação de ida do aeroporto. 695 00:45:11,280 --> 00:45:14,240 Realizando milhões de cálculos a cada segundo. 696 00:45:14,240 --> 00:45:17,040 EXPEDIDOR FALTO 697 00:45:21,720 --> 00:45:25,080 O algoritmo funciona tentando prever 698 00:45:25,080 --> 00:45:28,360 em que ordem a aeronave irá decolar. 699 00:45:28,360 --> 00:45:30,640 Se souber em que ordem eles podem decolar, 700 00:45:30,640 --> 00:45:32,560 então ele pode trabalhar de trás para frente e dizer: 701 00:45:32,560 --> 00:45:34,600 "Se precisar decolar neste momento, 702 00:45:34,600 --> 00:45:37,480 "então ele precisa entrar na fila da pista neste momento, 703 00:45:37,480 --> 00:45:39,840 "então ele precisa terminar o táxi neste momento, 704 00:45:39,840 --> 00:45:42,520 "então ele precisa iniciar sua operação de táxi neste momento. 705 00:45:42,520 --> 00:45:45,480 "Nesse caso, ele precisa terminar sua resistência a esta altura, 706 00:45:45,480 --> 00:45:47,600 "então ele precisa começar sua resistência a esta altura." 707 00:45:47,600 --> 00:45:50,600 E pode funcionar desde a hora em que deveria decolar 708 00:45:50,600 --> 00:45:52,640 a que horas deve começar a recuar. 709 00:45:55,440 --> 00:45:58,720 A saída do algoritmo é fornecida ao controle de tráfego aéreo 710 00:45:58,720 --> 00:46:01,560 através do sistema informático interno do aeroporto 711 00:46:01,560 --> 00:46:05,800 e exibido ao piloto no portão na forma de TSAT, 712 00:46:05,800 --> 00:46:07,800 o tempo de pushback recomendado. 713 00:46:10,000 --> 00:46:12,800 O piloto pode observar o sistema de entrada no estande 714 00:46:12,800 --> 00:46:15,960 para realmente ver a que horas ele espera partir. 715 00:46:17,880 --> 00:46:21,200 O maior benefício do algoritmo é que ele significa que você pode 716 00:46:21,200 --> 00:46:25,040 manter as aeronaves paradas por mais tempo sem que elas decolem mais tarde. 717 00:46:25,040 --> 00:46:28,440 Portanto, não há prejuízo para nenhum passageiro em termos de atrasos. 718 00:46:28,440 --> 00:46:30,840 O que você pode fazer é ligar seus motores mais tarde. 719 00:46:33,080 --> 00:46:35,480 Na verdade, se pouparmos dois minutos no tempo de táxi 720 00:46:35,480 --> 00:46:37,840 no caminho para o final da pista, ao longo de um ano, 721 00:46:37,840 --> 00:46:40,520 na verdade, isso representa uma economia de combustível no valor de A�15 milhões. 722 00:46:42,280 --> 00:46:46,240 O algoritmo de sequenciamento de Heathrow mostra exatamente o que pode ser realizado 723 00:46:46,240 --> 00:46:47,920 com a abordagem heurística. 724 00:46:49,040 --> 00:46:52,320 Assim como as abelhas, o algoritmo não encontra 725 00:46:52,320 --> 00:46:55,360 a solução absolutamente perfeita o tempo todo, 726 00:46:55,360 --> 00:46:58,720 mas mesmo assim torna um trabalho difícil um pouco mais fácil. 727 00:47:00,320 --> 00:47:02,080 Estamos muito orgulhosos do algoritmo 728 00:47:02,080 --> 00:47:05,720 porque na verdade agora, sentimos, modela o mundo real e é útil. 729 00:47:16,120 --> 00:47:19,080 No início, foram criados algoritmos 730 00:47:19,080 --> 00:47:21,640 de matemáticos para matemáticos. 731 00:47:21,640 --> 00:47:23,800 E ao longo do último século, 732 00:47:23,800 --> 00:47:26,400 algoritmos foram criados para computadores. 733 00:47:29,240 --> 00:47:33,960 Mas talvez a nossa relação esteja prestes a passar por uma revolução dramática. 734 00:47:39,720 --> 00:47:41,920 Na Microsoft Research em Cambridge, 735 00:47:41,920 --> 00:47:46,360 cientistas estão usando novas técnicas para desenvolver algoritmos... 736 00:47:46,360 --> 00:47:50,400 confundindo a fronteira entre o inventor e o próprio algoritmo. 737 00:47:56,600 --> 00:47:59,920 Este é o algoritmo de rastreamento esquelético do Kinect. 738 00:47:59,920 --> 00:48:02,760 O incrível é que ele é capaz de identificar 739 00:48:02,760 --> 00:48:04,920 as diferentes partes do meu corpo. 740 00:48:04,920 --> 00:48:08,360 Então você pode ver que o topo da minha cabeça está colorido de vermelho 741 00:48:08,360 --> 00:48:11,040 e minha mão direita aqui em azul. 742 00:48:11,040 --> 00:48:13,560 Você pode ver que meu pescoço está colorido de verde. 743 00:48:13,560 --> 00:48:16,080 Agora, esse algoritmo nunca me conheceu antes, 744 00:48:16,080 --> 00:48:18,760 não sabe como vou me mover no espaço, 745 00:48:18,760 --> 00:48:22,040 mas apenas usando os dados provenientes desta câmera especial aqui, 746 00:48:22,040 --> 00:48:25,520 medindo a distância da câmera ao meu corpo, 747 00:48:25,520 --> 00:48:28,120 é capaz de produzir este mapa. 748 00:48:30,520 --> 00:48:33,960 Qualquer que seja a postura que eu tome, usando nada mais do que a entrada 749 00:48:33,960 --> 00:48:36,360 da câmera especial com detecção de profundidade, 750 00:48:36,360 --> 00:48:39,360 o algoritmo é capaz de identificar com precisão, 751 00:48:39,360 --> 00:48:42,760 pixel por pixel, as diferentes partes do meu corpo. 752 00:48:46,640 --> 00:48:49,720 Foi desenvolvido para o console Microsoft Xbox 753 00:48:49,720 --> 00:48:53,640 para rastrear o movimento da postura corporal de um jogador em tempo real. 754 00:48:58,440 --> 00:49:01,600 Mas tão notável quanto o que este algoritmo pode fazer 755 00:49:01,600 --> 00:49:04,480 é o processo por trás de como foi criado, 756 00:49:04,480 --> 00:49:07,080 como explica o pesquisador Jamie Shotton. 757 00:49:09,640 --> 00:49:12,640 O que acontece é que cada pixel da imagem, 758 00:49:12,640 --> 00:49:16,080 estamos executando um algoritmo chamado árvore de decisão. 759 00:49:16,080 --> 00:49:19,520 E você pode pensar em uma árvore de decisão como um jogo de 20 questões. 760 00:49:19,520 --> 00:49:22,560 Então a árvore de decisão está pegando um pixel, digamos, na minha mão, 761 00:49:22,560 --> 00:49:25,320 e tentando decidir, OK, preciso colorir isso de azul 762 00:49:25,320 --> 00:49:28,480 - porque isso está na mão e não no meu corpo. - Sim. 763 00:49:28,480 --> 00:49:31,200 A chave para uma árvore de decisão é o fato de que as 20 questões 764 00:49:31,200 --> 00:49:33,880 que você pergunta não são os mesmos 765 00:49:33,880 --> 00:49:37,000 para cada pixel que estamos tentando classificar. 766 00:49:37,000 --> 00:49:39,680 E o conjunto completo de possíveis perguntas 767 00:49:39,680 --> 00:49:43,080 que poderia ser respondida é exponencial. 768 00:49:43,080 --> 00:49:46,360 - São dois elevado a vinte. - Certo, tudo bem. São mais de um milhão de perguntas, 769 00:49:46,360 --> 00:49:49,240 muitas perguntas que você terá que programar aí. 770 00:49:49,240 --> 00:49:51,080 Sim. Levaria muito tempo 771 00:49:51,080 --> 00:49:55,120 e ser muito propenso a erros para que nós, como humanos, programemos isso manualmente. 772 00:49:55,120 --> 00:49:58,760 - Então, o algoritmo está se escrevendo sozinho, ou...? - Absolutamente. 773 00:50:02,960 --> 00:50:05,520 O algoritmo não foi projetado por Jamie 774 00:50:05,520 --> 00:50:08,960 mas sim por meio de um processo chamado aprendizado de máquina. 775 00:50:11,440 --> 00:50:15,720 Envolveu mostrar ao algoritmo milhões de imagens de treinamento, 776 00:50:15,720 --> 00:50:19,320 de corpos em diferentes poses e de diversas formas e tamanhos, 777 00:50:19,320 --> 00:50:23,600 do muito gordo ao muito magro, do muito baixo ao muito alto. 778 00:50:24,640 --> 00:50:28,880 E a partir disso, o algoritmo aprendeu essencialmente por exemplo, 779 00:50:28,880 --> 00:50:31,040 elaborando suas próprias regras. 780 00:50:34,200 --> 00:50:37,760 Onde entra nossa inteligência como projetistas do sistema 781 00:50:37,760 --> 00:50:41,240 não está na programação do algoritmo, por si só, 782 00:50:41,240 --> 00:50:44,200 mas ao projetar o conjunto de dados de treinamento 783 00:50:44,200 --> 00:50:48,160 para capturar todos os tipos de variações que esperamos ver 784 00:50:48,160 --> 00:50:51,040 quando implantamos este sistema nas salas de estar das pessoas 785 00:50:51,040 --> 00:50:52,360 para jogar seus jogos. 786 00:50:52,360 --> 00:50:55,600 Então, no final das contas, você realmente sabe o que o algoritmo está fazendo? 787 00:50:55,600 --> 00:50:57,800 Podemos ter uma noção do que ele está tentando fazer 788 00:50:57,800 --> 00:50:59,400 e como está funcionando aproximadamente, 789 00:50:59,400 --> 00:51:02,960 mas não poderíamos realmente entender o que exatamente está acontecendo. 790 00:51:04,960 --> 00:51:09,920 A mesma abordagem de aprendizado de máquina foi usada em outras aplicações. 791 00:51:09,920 --> 00:51:14,680 Por exemplo, este algoritmo é capaz de fazer algo que por muito tempo 792 00:51:14,680 --> 00:51:19,560 era considerada uma habilidade exclusiva de neurocirurgiões e radiologistas. 793 00:51:19,560 --> 00:51:22,800 A partir de uma ressonância magnética, o algoritmo pode identificar 794 00:51:22,800 --> 00:51:26,480 e mapear um tumor cerebral em 3-D. 795 00:51:26,480 --> 00:51:29,280 O que significa que um trabalho que normalmente leva uma hora 796 00:51:29,280 --> 00:51:31,360 pode ser feito em questão de minutos. 797 00:51:34,640 --> 00:51:37,640 O professor Chris Bishop está interessado em desenvolver 798 00:51:37,640 --> 00:51:40,880 o conceito de aprendizado de máquina ainda mais. 799 00:51:40,880 --> 00:51:44,680 Para criar algoritmos que possam aprender como nós, 800 00:51:44,680 --> 00:51:46,600 diretamente da experiência. 801 00:51:49,160 --> 00:51:52,120 Então esta demonstração, eu acho, ilustra a direção 802 00:51:52,120 --> 00:51:54,120 que os algoritmos irão nos próximos anos. 803 00:51:54,120 --> 00:51:57,640 OK, posso ver muitos filmes aqui, então o que o algoritmo vai fazer? 804 00:51:57,640 --> 00:52:00,760 Temos algumas centenas dos filmes mais assistidos, 805 00:52:00,760 --> 00:52:02,240 e o que vai fazer, 806 00:52:02,240 --> 00:52:06,600 vai aprender sobre seus gostos e desgostos pessoais. 807 00:52:06,600 --> 00:52:08,080 Já foi treinado, 808 00:52:08,080 --> 00:52:11,080 então é um algoritmo de aprendizado de máquina nos bastidores, 809 00:52:11,080 --> 00:52:14,480 mas já foi treinado com dados de cerca de 10 mil pessoas. 810 00:52:14,480 --> 00:52:18,160 O que vai fazer agora é aprender sobre suas preferências. 811 00:52:18,160 --> 00:52:20,200 No momento não sabe nada sobre você, 812 00:52:20,200 --> 00:52:22,760 então esses filmes são organizados aleatoriamente na tela. 813 00:52:22,760 --> 00:52:25,440 O que preciso que você faça é encontrar um desses filmes, 814 00:52:25,440 --> 00:52:28,120 seja aquele que você gosta ou aquele que você não gosta. 815 00:52:28,120 --> 00:52:31,160 Se gostar, você pode arrastá-lo para a região verde, 816 00:52:31,160 --> 00:52:33,600 se não gostar, vá para a região vermelha. 817 00:52:33,600 --> 00:52:35,600 Rushmore, sou um grande fã de Rushmore. 818 00:52:35,600 --> 00:52:37,560 Você gosta de Rushmore? OK, certo. 819 00:52:37,560 --> 00:52:41,120 Então o que está acontecendo agora é que se um filme estiver no lado direito 820 00:52:41,120 --> 00:52:44,760 - perto da região verde, tem muita certeza que você vai gostar. - OK. 821 00:52:44,760 --> 00:52:46,600 Então aqui embaixo perto da região vermelha, 822 00:52:46,600 --> 00:52:48,560 está muito confiante de que você não vai gostar. 823 00:52:48,560 --> 00:52:51,400 No meio, é 50-50. Realmente não sabe. 824 00:52:51,400 --> 00:52:54,320 Então, se eu escolher um filme no meio aqui, 825 00:52:54,320 --> 00:52:57,680 Não sou um grande fã de Austin Powers, então vamos filmar essa... 826 00:52:57,680 --> 00:53:00,800 Então você vê, eles estão começando a se espalhar lateralmente, 827 00:53:00,800 --> 00:53:04,480 - vai ficar um pouco mais confiante. - É muito bom. 828 00:53:04,480 --> 00:53:07,480 Sou um grande fã do Dr Strangelove 829 00:53:07,480 --> 00:53:11,480 e sou um grande fã de Woody Allen, 830 00:53:11,480 --> 00:53:14,520 mas Spinal Tap acha que vou gostar disso. 831 00:53:14,520 --> 00:53:18,040 Então isso é interessante, então quando tiver certeza de que você gostou deles 832 00:53:18,040 --> 00:53:19,800 e você disse que gostou deles, 833 00:53:19,800 --> 00:53:22,920 não aconteceu muita coisa porque não aprendeu muito. 834 00:53:22,920 --> 00:53:25,840 Quando tinha certeza de que você gostaria, no caso do Spinal Tap 835 00:53:25,840 --> 00:53:28,280 e você disse: “Não gosto disso”, houve uma grande mudança. 836 00:53:28,280 --> 00:53:30,200 Está aprendendo coisas comigo. 837 00:53:30,200 --> 00:53:33,080 Na verdade, estou mudando o algoritmo à medida que interajo com ele. 838 00:53:33,080 --> 00:53:36,520 Exatamente. Enquanto o Kinect foi treinado em laboratório e depois congelado, 839 00:53:36,520 --> 00:53:38,560 este algoritmo continua a se adaptar 840 00:53:38,560 --> 00:53:41,280 e continua a evoluir ao longo de sua vida. 841 00:53:41,280 --> 00:53:44,120 Quanto mais filmes você avaliar como gostando ou não gostando, 842 00:53:44,120 --> 00:53:45,960 mais ele sabe sobre você pessoalmente 843 00:53:45,960 --> 00:53:48,760 e mais capaz será de fazer boas recomendações. 844 00:53:48,760 --> 00:53:52,320 Este algoritmo está começando a parecer muito mais humano 845 00:53:52,320 --> 00:53:54,840 na forma como interage com o mundo. 846 00:53:54,840 --> 00:53:57,840 É esse o seu objetivo, encontrar uma maneira de produzir algoritmos 847 00:53:57,840 --> 00:54:00,560 que são um pouco parecidas com a forma como negociamos o mundo? 848 00:54:00,560 --> 00:54:03,720 Exatamente. É um passo adiante nesse longo caminho para a produção de máquinas 849 00:54:03,720 --> 00:54:05,880 que realmente são tão capazes quanto o cérebro humano. 850 00:54:05,880 --> 00:54:08,720 Temos um longo caminho a percorrer, mas este é um pequeno passo nessa direção 851 00:54:08,720 --> 00:54:10,160 porque não está mais consertado. 852 00:54:10,160 --> 00:54:12,480 Agora continua aprendendo da mesma maneira 853 00:54:12,480 --> 00:54:14,800 que continuamos aprendendo em nossa vida diária. 854 00:54:19,680 --> 00:54:21,680 Acho que estamos apenas começando 855 00:54:21,680 --> 00:54:24,240 para aproveitar todo o potencial dos algoritmos 856 00:54:24,240 --> 00:54:26,600 e tenho mais um lugar que quero visitar, 857 00:54:26,600 --> 00:54:28,840 que me disseram que me dará um vislumbre 858 00:54:28,840 --> 00:54:31,760 do quanto eles são capazes de fazer por nós. 859 00:54:40,600 --> 00:54:43,600 É um mundo onde quase tudo é automatizado. 860 00:54:46,920 --> 00:54:49,400 Onde os algoritmos estão no controle. 861 00:54:49,400 --> 00:54:53,920 É o maior armazém automatizado de mercearia do planeta. 862 00:54:53,920 --> 00:54:57,520 Pertence ao varejista de alimentos on-line Ocado 863 00:54:57,520 --> 00:55:01,000 e equivale a 45 supermercados em um. 864 00:55:02,720 --> 00:55:06,600 Mais de dois milhões de itens passam por este armazém todos os dias. 865 00:55:06,600 --> 00:55:10,360 A qualquer momento, existem cerca de 7.000 caixas 866 00:55:10,360 --> 00:55:12,800 percorrendo mais de 25 quilômetros de pista, 867 00:55:12,800 --> 00:55:18,360 e controlar todos os aspectos deste espetáculo surpreendente são algoritmos. 868 00:55:25,520 --> 00:55:29,120 Cada uma dessas caixas vermelhas faz parte de um pedido do cliente 869 00:55:29,120 --> 00:55:32,880 e eles podem continuar a partir daqui para encontrar outros itens 870 00:55:32,880 --> 00:55:35,160 que eles querem no armazém, 871 00:55:35,160 --> 00:55:37,280 até que eles finalmente terminem, 872 00:55:37,280 --> 00:55:41,360 carregado em uma van e depois conduzido pelo nosso sistema de roteamento 873 00:55:41,360 --> 00:55:43,720 numa rota que, em muitos aspectos, 874 00:55:43,720 --> 00:55:47,360 está resolvendo problemas como o problema do caixeiro viajante. 875 00:55:47,360 --> 00:55:49,720 Há decisões sendo tomadas em todos os lugares 876 00:55:49,720 --> 00:55:52,240 como uma caixa vermelha vai para um lado e para outro. 877 00:55:52,240 --> 00:55:55,600 A complexidade por trás de tudo isso está além 878 00:55:55,600 --> 00:55:58,760 o que qualquer humano poderia controlar ou resolver, 879 00:55:58,760 --> 00:56:01,760 e é aí que esses algoritmos, 880 00:56:01,760 --> 00:56:03,960 essas técnicas de resolução de problemas entram 881 00:56:03,960 --> 00:56:05,920 para superar esses desafios. 882 00:56:11,000 --> 00:56:15,480 Para onde quer que você olhe, a mão invisível do algoritmo está trabalhando. 883 00:56:16,560 --> 00:56:20,360 Algoritmos de previsão monitoram e reabastecem o estoque 884 00:56:20,360 --> 00:56:24,720 de mais de 43 mil produtos, antecipando a demanda dos clientes. 885 00:56:26,760 --> 00:56:29,840 Algoritmos do sistema de controle gerenciam o tráfego 886 00:56:29,840 --> 00:56:33,320 das mais de 7.000 caixas espalhadas pelo armazém. 887 00:56:36,360 --> 00:56:39,800 E algoritmos de roteamento de vans controlam o movimento da frota 888 00:56:39,800 --> 00:56:41,960 de mais de 1.500 vans, 889 00:56:41,960 --> 00:56:46,240 testando mais de quatro milhões de combinações de rotas diferentes a cada segundo. 890 00:56:48,120 --> 00:56:51,160 Você quase pode ver a mente da máquina trabalhando 891 00:56:51,160 --> 00:56:54,360 e não é um processo estático, é por isso que há uma quantidade enorme 892 00:56:54,360 --> 00:56:59,520 de aprendizado de máquina aqui, então é como um organismo auto-adaptável. 893 00:56:59,520 --> 00:57:02,200 É preciso aprender constantemente como fazer melhor. 894 00:57:02,200 --> 00:57:04,360 As pessoas não poderiam fazer isso. 895 00:57:04,360 --> 00:57:06,600 A máquina tem que se ajustar. 896 00:57:10,640 --> 00:57:14,080 Então, quem você diria que estava realmente no controle de tudo? 897 00:57:14,080 --> 00:57:17,400 Em última análise, são os algoritmos que estão no controle. 898 00:57:17,400 --> 00:57:19,960 Acho que estou tendo ondas de calor algorítmicas 899 00:57:19,960 --> 00:57:22,080 olhando para essa coisa incrível! 900 00:57:24,440 --> 00:57:26,560 Em certo sentido, este armazém é como 901 00:57:26,560 --> 00:57:28,880 um pequeno microcosmo do mundo moderno. 902 00:57:28,880 --> 00:57:32,640 Os algoritmos executam tudo, desde mecanismos de pesquisa na Internet, 903 00:57:32,640 --> 00:57:35,680 navegação por satélite, até mesmo mantendo nossos cartões de crédito seguros. 904 00:57:35,680 --> 00:57:39,680 Nosso mundo não funcionaria sem o poder desses algoritmos. 905 00:57:45,440 --> 00:57:48,920 A Open University produziu um pacote gratuito para você aprender, 906 00:57:48,920 --> 00:57:52,880 crie e descubra mais sobre a tecnologia digital do passado e do presente. 907 00:57:52,880 --> 00:57:55,280 Para encomendar o seu exemplar, ligue... 908 00:57:58,560 --> 00:58:00,080 ..ou siga o link abaixo 909 00:58:00,080 --> 00:58:01,680 para a Universidade Aberta.